We study the problem of finding the minimum-length curvature constrained\r\nclosed path through a set of regions in the plane. This problem is referred to as the Dubins\r\nTraveling Salesperson Problem with Neighborhoods (DTSPN). An algorithm is presented\r\nthat uses sampling to cast this infinite dimensional combinatorial optimization problem as a\r\nGeneralized Traveling Salesperson Problem (GTSP) with intersecting node sets. The GTSP\r\nis then converted to an Asymmetric Traveling Salesperson Problem (ATSP) through a series\r\nof graph transformations, thus allowing the use of existing approximation algorithms. This\r\nalgorithm is shown to perform no worse than the best existing DTSPN algorithm and is\r\nshown to perform significantly better when the regions overlap. We report on the application\r\nof this algorithm to route an Unmanned Aerial Vehicle (UAV) equipped with a radio to\r\ncollect data from sparsely deployed ground sensors in a field demonstration of autonomous\r\ndetection, localization, and verification of multiple acoustic events.
Loading....